package com.cty._04_Optimization._39_MoreThanHalfNum;

/**
 * @Auther: cty
 * @Date: 2020/7/15 9:55
 * @Description: 面试题39：数组中出现次数超过一半的数字
 * 题目：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例
 * 如输入一个长度为9的数组{1, 2, 3, 2, 2, 2, 5, 4, 2}。由于数字2在数组中
 * 出现了5次，超过数组长度的一半，因此输出2。
 * @version: 1.0
 */
public class MoreThanHalfNum {
    /**
     * 方法一：不修改数组
     * @param array
     * @param length
     * @return
     */
    public static int moreThanHalfNum(int[] array, int length){
        if(array==null || length==0)
            return 0;

        int result = array[0];
        int times = 0;

        // 查找数字
        for(int i=0; i<length; i++){
            if(times == 0)
                result = array[i];
            else if(result == array[i])
                times++;
            else
                times--;
        }  // end for()

        if(!checkMoreThanHalf(array,length,result))
            return 0;
        return result;
    }  // end method


    /**
     * 方法二：修改数组（划分实现）
     * @param array
     * @param length
     * @return
     */
    public static int moreThanHalfNum2(int[] array, int length) {
        if(array==null || length==0)
            return 0;

        int middle = length>>1;
        int start = 0;
        int end = length - 1;
        int index = partition(array,length,start,end);
        while(index != middle){
            if(index > middle)
                end = index - 1;
            else
                start = index + 1;
            index = partition(array,length,start,end);
        }  // end while
        int result = array[index];

        if(!checkMoreThanHalf(array,length,result))
            return 0;
        return result;
    }  // end method


    // 验证是否该数字出现次数超过数组长度的一半
    private static boolean checkMoreThanHalf(int[] array, int length, int result){
        int times = 0;
        for(int i=0; i<length; i++)
            if(result == array[i])
                times++;

        if(times<<1 > length)
            return true;
        else
            return false;
    }  // end checkMoreThanHalf()


    // 划分
    private static int partition(int[] array, int length, int start, int end) {
        if(array==null || length<=0 || start<0 || end >=length)
            return -1;

        int pivotIndex = randomInRange(start, end);  // 获取枢纽索引
        int pivot = array[pivotIndex];
        swap(array, pivotIndex, end);  // 将枢纽与数组末尾值交换位置

        int leftPtr = start-1;
        int rightPtr = end;
        while(true){
            while(array[++leftPtr] < pivot);  // 从左向右遇到大于等于枢纽值停止（到达索引为end位置必停）
            while(rightPtr>start && array[--rightPtr]>pivot);  // 从右向左遇到小于等于枢纽值或到达索引为start位置停止

            if(leftPtr >= rightPtr)
                break;

            swap(array, leftPtr, rightPtr);
        }  // end while

        swap(array,leftPtr,end);  // 将枢纽值移到中间
        return leftPtr;
    }  // end partition()


    // 交换数组中两个索引位置处的值
    private static void swap(int[] array, int a, int b){
        int temp = array[a];
        array[a] = array[b];
        array[b] = temp;
    }  // end swap()


    // 获取指定范围的随机数
    private static int randomInRange(int start, int end){
        if(end < start)
            return 0;
        return start + (int)(Math.random()*(end-start+1));
    }  // end randomInRange()

}  // end class
